package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/'>子数组不同元素数目的平方和 I(Subarrays Distinct Element Sum of Squares I)</a>
 * <p>给你一个下标从 0 开始的整数数组 nums 。</p>
 * <p>
 * 定义 nums 一个子数组的 不同计数 值如下：
 *     <ul>
 *         <li>令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。</li>
 *     </ul>
 * </p>
 * <p>请你返回 nums 中所有子数组的 不同计数 的 平方 和。</p>
 * <p>由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。</p>
 * <p>子数组指的是一个数组里面一段连续 非空 的元素序列。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,2,1]
 *      输出：15
 *      解释：六个子数组分别为：
 *          [1]: 1 个互不相同的元素。
 *          [2]: 1 个互不相同的元素。
 *          [1]: 1 个互不相同的元素。
 *          [1,2]: 2 个互不相同的元素。
 *          [2,1]: 2 个互不相同的元素。
 *          [1,2,1]: 2 个互不相同的元素。
 *          所有不同计数的平方和为 1^2 + 1^2 + 1^2 + 2^2 + 2^2 + 2^2 = 15 。
 *
 * 示例 2：
 *      输入：nums = [2,2]
 *      输出：3
 *      解释：三个子数组分别为：
 *          [2]: 1 个互不相同的元素。
 *          [2]: 1 个互不相同的元素。
 *          [2,2]: 1 个互不相同的元素。
 *          所有不同计数的平方和为 1^2 + 1^2 + 1^2 = 3 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= nums.length <= 100</li>
 *      <li>1 <= nums[i] <= 100</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/24 16:20
 */
public class LC2913SubarraysDistinctElementSumOfSquares_I_S {

    static class Solution {

        public int sumCounts(List<Integer> nums) {
            final int MOD = 1000000007;
            int res = 0;
            Set<Integer> set = new HashSet<>();
            // 从第一个元素开始
            for (int i = 0; i < nums.size(); i++) {
                // 第一次取 1 个，第二次取 2个...，第 n 次 取 n个。
                // 例如：1，2，1
                // 第一轮：1    1,2    1,2,1        => 1 + 4 + 4 = 9
                // 第二轮：2    2,1                 => 1 + 4     = 5
                // 第三轮：1                        => 1         = 1

                // 例如：1，2，3，4
                // 第一轮：1    1,2    1,2,3    1,2,3,4
                // 第二轮：2    2,3    2,3,4
                // 第三轮：3    3,4
                // 第四轮：4
                for (int j = i; j < nums.size(); j++) {
                    set.add(nums.get(j));
                    res += set.size() * set.size();
                    res %= MOD;
                }
                set.clear();
            }
            return res;
        }

        public int sumCounts2(List<Integer> nums) {
            final int MOD = (int) (1e9 + 7);
            int res = 0;
            Map<Integer, Integer> map = new HashMap<>();
            // 从第一个元素开始
            for (int i = 0; i < nums.size(); i++) {
                // 第一次取 1 个，第二次取 2个...，第 n 次 取 n个。
                // 例如：1，2，1
                // 第一轮：1    1,2    1,2,1        => 1 + 4 + 4 = 9
                // 第二轮：2    2,1                 => 1 + 4     = 5
                // 第三轮：1                        => 1         = 1
                for (int j = i; j < nums.size(); j++) {
                    map.put(nums.get(j), map.getOrDefault(nums.get(j), 0) + 1);
                    res += map.size() * map.size();
                    res %= MOD;
                }
                map.clear();
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.sumCounts(Arrays.asList(1, 2, 1)));
        System.out.println(solution.sumCounts(Arrays.asList(2, 2)));
    }
}
